package code2;

import java.util.Arrays;

/**
 * @author noob
 * @version 1.0
 * @date 2021/3/16 10:27
 * 自底向上的归并排序
 */
public class MergeSort {






    // 自底向上的归并排序
    public static <E extends Comparable<E>> void sortBU(E[] data){

        E[] temp = Arrays.copyOf(data,data.length);

        int n  = data.length;

        //遍历合并区间的长度
        for (int sz = 1; sz < n  ; sz+= sz) {

            //遍历合并的两个区间的起始位置  i
            // 合并 [i, i + sz - 1] 和 [i + sz, Math.min(i + sz + sz - 1, n - 1)]
            for (int i = 0; i + sz < n;  i+=sz+sz) {
                if(data[i + sz - 1].compareTo(data[i + sz]) > 0)
                    merge(data, i, i + sz - 1, Math.min(i + sz + sz - 1, n - 1), temp);
            }
        }
    }

    private static <E extends Comparable<E>> void merge(E[] data, int left, int mid, int right, E[] temp){

        System.arraycopy(data, left, temp, left, right - left + 1);

        int i = left, j = mid + 1;

        // 每轮循环为 data[k] 赋值
        for(int k = left; k <= right; k ++){

            if(i > mid){
                data[k] = temp[j]; j ++;
            }
            else if(j > right){
                data[k] = temp[i]; i ++;
            }
            else if(temp[i].compareTo(temp[j]) <= 0){
                data[k] = temp[i]; i ++;
            }
            else{
                data[k] = temp[j]; j ++;
            }
        }
    }









    public static void main(String[] args) {
        int n = 10000000;

        Integer[] arr = ArrayGenerator.generateRandomArray(n, n);
        Integer[] arr2 = Arrays.copyOf(arr, arr.length);

        SortHelper.sortTest("MergeSortBU", arr2);
    }
}
